package class_0905DynamicPrograming;
/**
 * 曲折穷途天地窄,重重灾劫生死危.
 * 身入柳絮随风扬,无论云泥意贯一.---柳贯一
 */

/**
 *  规则怪谈:
 *  假设有排成一行的N个位置,记为1~N, N一定大于等于2.
 *  初始位置:M ,M在1~N的一个.
 *  若机器人来到1位置,那么下前进
 *  若机器人来到n位置,那么只能回退.
 *  机器人每次走一步.
 *
 * method:从顶向下的动态规划(计划搜索法)
 * 动态规划:牺牲空间换时间,当然有些特定情况,动态规划法也可以省空间.
 */
public class coding_RobetWalk {
    /**
     * 主方法
     * @param N 范围
     * @param start 起始点
     * @param aim 目的地
     * @param K 位置
     * @return
     */
    public static int ways1(int N, int start, int aim, int K){
        //检查传参,防止杠精搞特殊输入把程序搞崩了.
        return process1(start ,K , aim , N);
    }
    private static int process1(int cur, int rest, int aim, int N){
        if(rest==0){
            return cur==aim?1:0;
        }
        //rest>0,怎么走.
        /**
         * 题目条件已经给出分类讨论的情况`
         */
        if(cur==1){
            return process1(cur+1,rest - 1, aim, N);
        }
        else if(cur==N){
            return process1(cur-1,rest - 1, aim,N);
        }
        else{
            return process1(cur-1,rest - 1,aim,N) + process1(cur+1,rest-1,aim,N);
        }
    }
    /**
     *     空间换时间
     */
    public static int ways2(int N, int start , int aim, int K){
        //why so design?
        int[][] dp = new int[N+1][K+1];
        for (int i = 0; i < N+1; i++) {
            for (int j = 0; j < K+1; j++) {
                //设置-1表示无效状态.
                dp[i][j]=-1;
            }
        }
        return  process2(start, K ,aim ,N,dp);
    }

    /**
     * 子问题重叠,直接通过dp数组查值,不用重复递归跑一遍.
     * 缓存法-dp数组
     * @param cur   cur [1,n]
     * @param rest   rest [0,K]
     * @param aim  目标位置
     * @param N   总的范围[1,N]
     * @param dp  缓存数组
     * @return
     */
    private static int process2(int cur, int rest, int aim, int N, int[][] dp) {
        //计算过,直接取值
        if(dp[cur][rest]!=1){
            return dp[cur][rest];
        }
        //跟踪记录缓存.
        int ans = 0;
        if(rest==0){
            ans =  cur==aim?1:0;
        }
        else if(cur==1){
            ans = process2(cur+1,rest - 1, aim, N ,dp);
        }
        else if(cur==N){
            ans =  process2(cur-1,rest - 1, aim,N , dp);
        }
        else{
            ans = process2(cur-1,rest - 1, aim, N , dp) + process2(cur+1,rest-1,aim,N, dp);
        }
        dp[cur][rest] = ans;
        return ans;
    }
    /**
     * 省空间的方法
     * 有向无环图
     * 撞墙杨辉三角
     */
    public static int ways3(int N, int start , int aim, int K) {
        int[][] dp = new int[N+1][K+1];
        dp[aim][0] = 1;//其余数组默认为0;
        for (int j = 1; j <= K; j++) { //列
            dp[1][j] = dp[2][j-1];
            for (int i = 2; i <=N ; i++) {
                //行
                dp[i][j] = dp[i+1][j-1] +  dp[i-1][j-1];
            }
            dp[N][j] = dp[N-1][j-1];
        }
            return dp[start][K] ;
    }
}

/**
 * 我......我曹,直观法
 *
 */

/**
 * 规则怪谈:
 * 给定一个整型数组, 代表数值不同的纸牌排成一条线
 * 玩家A,B依次取走那走每张牌.
 * 玩家A先拿,B后拿.
 * 每个玩家只能拿最左或者最右.
 * 玩家A,B足够机灵和智慧.且不打感情牌.
 * 返回最后获胜者分数.
 */
class Coding_getPOK{
    //[50,100,20,10]
    //那么AB开始比赛吧
    public static int win1(int[] arr){
        if(arr==null||arr.length==1){
            return 0;//无效数据
        }
        int first = f(arr,0,arr.length-1);
        int second = g(arr, 0 , arr.length - 1);
        if(first==second){
            return -1;//平分胜负.
        }
        return Math.max(first,second);
    }
    //A先手
    public static int f(int[] arr, int L, int R){
        if(L==R){
            return arr[R];
        }else{
            int p1 = arr[L] + g(arr, L+1, R);
            int p2 = arr[R] + g(arr, L, R-1);
            return Math.max(p1,p2);
        }
    }
    //B打反手
    public static int g(int[] arr, int L, int R) {
        if(L==R){
            return 0;
        }
        else{
            int p1 = f(arr, L+1, R);
            int p2 = f(arr, L, R-1);
            return Math.min(p1,p2);
        }
    }


    public static int win2(int[] arr){
        if(arr==null||arr.length==1){
            return 0;//无效数据
        }
        int N = arr.length;
        int[][] fmap = new int[N][N];
        int[][] gmap = new int[N][N];
        for(int i=0;i<N;i++){
            for(int j=0;j<N;j++){
                fmap[i][j] = -1;
                gmap[i][j] = -1;
            }
        }
        int first = f2(arr,0,arr.length-1,fmap,gmap);
        int second = g2(arr, 0 , arr.length - 1,fmap,gmap);
        return Math.max(first,second);
    }
    public static int f2(int[] arr, int L, int R, int[][] fmap, int[][] gmap){
        if(fmap[L][R]==-1){
            return fmap[L][R];
        }
        int ans = 0;
        if(L==R){
            ans = arr[L];
        }else{
            int p1 = arr[L] + g2(arr, L+1, R,fmap, gmap);
            int p2 = arr[R] + g2(arr, L, R-1, fmap, gmap);
            ans = Math.max(p1,p2);
        }
        fmap[L][R] = ans;
        return ans;
    }
    public static int g2(int[] arr, int L, int R, int[][] fmap, int[][] gmap){
        if(gmap[L][R]==-1){
            return gmap[L][R];
        }
        int ans = 0;
        if(L==R){
            ans = 0;
        }else{
            int p1 = f2(arr, L+1, R,fmap, gmap);
            int p2 = f2(arr, L, R-1, fmap, gmap);
            ans = Math.min(p1,p2);
        }
        gmap[L][R] = ans;
        return ans;
    }
    public static int win3(int[] arr){
        return 0;
    }
}
